class Solution
{
public:
    vector<int> prevPermOpt1(vector<int> &arr)
    {
        int n = arr.size();
        int minVal = arr[n - 1];
        int haveLessPos = -1;
        for (int i = n - 2; i >= 0; --i)
        {
            if (arr[i] > minVal)
            {
                haveLessPos = i;
                break;
            }
            else
            {
                minVal = arr[i];
            }
        }

        if (haveLessPos == -1)
        {
            return arr;
        }

        int maxOfLess = -1;
        int maxOfLessPos = -1;
        for (int i = haveLessPos + 1; i < n; ++i)
        {
            if (arr[i] > maxOfLess && arr[i] < arr[haveLessPos])
            {
                maxOfLess = arr[i];
                maxOfLessPos = i;
            }
        }

        swap(arr[haveLessPos], arr[maxOfLessPos]);
        return arr;
    }
};